home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / documents / RFC / rfc815.txt < prev    next >
Text File  |  1994-08-01  |  15KB  |  454 lines

  1.  
  2.  
  3. RFC:  815
  4.  
  5.  
  6.  
  7.                    IP DATAGRAM REASSEMBLY ALGORITHMS
  8.  
  9.                              David D. Clark
  10.                   MIT Laboratory for Computer Science
  11.                Computer Systems and Communications Group
  12.                                July, 1982
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.      1.  Introduction
  20.  
  21.  
  22.      One of the mechanisms of IP is fragmentation and reassembly.  Under
  23.  
  24. certain  circumstances,  a  datagram  originally transmitted as a single
  25.  
  26. unit will arrive at its final destination broken into several fragments.
  27.  
  28. The IP layer at the receiving host must accumulate these fragments until
  29.  
  30. enough have arrived to completely reconstitute  the  original  datagram.
  31.  
  32. The  specification  document  for IP gives a complete description of the
  33.  
  34. reassembly mechanism, and contains several examples.  It  also  provides
  35.  
  36. one  possible  algorithm  for  reassembly,  based  on  keeping  track of
  37.  
  38. arriving fragments in a vector of bits.    This  document  describes  an
  39.  
  40. alternate approach which should prove more suitable in some machines.
  41.  
  42.  
  43.      A  superficial  examination  of  the reassembly process may suggest
  44.  
  45. that it is rather complicated.  First, it is necessary to keep track  of
  46.  
  47. all the fragments, which suggests a small bookkeeping job.  Second, when
  48.  
  49. a  new fragment arrives, it may combine with the existing fragments in a
  50.  
  51. number of different ways.  It may precisely fill the space  between  two
  52.  
  53. fragments,  or  it  may  overlap  with existing fragments, or completely
  54.  
  55.                                    2
  56.  
  57.  
  58. duplicate  existing  fragments,  or  partially  fill a space between two
  59.  
  60. fragments without abutting either of them.  Thus, it might seem that the
  61.  
  62. reassembly  process  might  involve  designing  a   fairly   complicated
  63.  
  64. algorithm that tests for a number of different options.
  65.  
  66.  
  67.      In  fact,  the  process  of  reassembly  is  extremely simple. This
  68.  
  69. document describes a way of dealing with reassembly  which  reduces  the
  70.  
  71. bookkeeping  problem  to  a minimum, which requires for storage only one
  72.  
  73. buffer equal in size to the final datagram being reassembled, which  can
  74.  
  75. reassemble a datagram from any number of fragments arriving in any order
  76.  
  77. with  any  possible  pattern  of  overlap  and duplication, and which is
  78.  
  79. appropriate for almost any sort of operating system.
  80.  
  81.  
  82.      The reader should consult the IP specification document to be  sure
  83.  
  84. that  he  is completely familiar with the general concept of reassembly,
  85.  
  86. and the particular header fields and vocabulary  used  to  describe  the
  87.  
  88. process.
  89.  
  90.  
  91.      2.  The Algorithm
  92.  
  93.  
  94.      In  order  to  define this reassembly algorithm, it is necessary to
  95.  
  96. define some terms.  A partially reassembled datagram consists of certain
  97.  
  98. sequences of octets that have already arrived, and certain  areas  still
  99.  
  100. to  come.    We will refer to these missing areas as "holes".  Each hole
  101.  
  102. can be characterized by two numbers, hole.first, the number of the first
  103.  
  104. octet in the hole, and hole.last, the number of the last  octet  in  the
  105.  
  106. hole.    This pair of numbers we will call the "hole descriptor", and we
  107.  
  108. will assume that all of the hole descriptors for a  particular  datagram
  109.  
  110. are gathered together in the "hole descriptor list".
  111.  
  112.                                    3
  113.  
  114.  
  115.      The  general  form  of  the  algorithm  is  as follows.  When a new
  116.  
  117. fragment of the datagram arrives, it will possibly fill in one  or  more
  118.  
  119. of  the existing holes.  We will examine each of the entries in the hole
  120.  
  121. descriptor list to see whether the hole in  question  is  eliminated  by
  122.  
  123. this incoming fragment.  If so, we will delete that entry from the list.
  124.  
  125. Eventually, a fragment will arrive which eliminates every entry from the
  126.  
  127. list.    At this point, the datagram has been completely reassembled and
  128.  
  129. can be passed to higher protocol levels for further processing.
  130.  
  131.  
  132.      The algorithm will be described in two phases. In the  first  part,
  133.  
  134. we  will  show  the  sequence  of  steps  which  are executed when a new
  135.  
  136. fragment arrives, in order to  determine  whether  or  not  any  of  the
  137.  
  138. existing  holes  are  filled by the new fragment.  In the second part of
  139.  
  140. this description, we will  show  a  ridiculously  simple  algorithm  for
  141.  
  142. management of the hole descriptor list.
  143.  
  144.  
  145.      3.  Fragment Processing Algorithm
  146.  
  147.  
  148.      An arriving fragment can fill any of the existing holes in a number
  149.  
  150. of ways.  Most simply, it can completely fill a hole.  Alternatively, it
  151.  
  152. may  leave some remaining space at either the beginning or the end of an
  153.  
  154. existing hole.  Or finally, it can lie in  the  middle  of  an  existing
  155.  
  156. hole,  breaking the hole in half and leaving a smaller hole at each end.
  157.  
  158. Because of these possibilities, it might seem that  a  number  of  tests
  159.  
  160. must  be  made  when  a  new  fragment  arrives,  leading  to  a  rather
  161.  
  162. complicated algorithm.  In fact, if properly  expressed,  the  algorithm
  163.  
  164. can compare each hole to the arriving fragment in only four tests.
  165.  
  166.                                    4
  167.  
  168.  
  169.      We  start  the algorithm when the earliest fragment of the datagram
  170.  
  171. arrives.  We begin by creating an empty data buffer area and putting one
  172.  
  173. entry in its  hole  descriptor  list,  the  entry  which  describes  the
  174.  
  175. datagram  as  being completely missing.  In this case, hole.first equals
  176.  
  177. zero, and hole.last equals infinity. (Infinity is presumably implemented
  178.  
  179. by a very large integer, greater than 576, of the implementor's choice.)
  180.  
  181. The following eight steps are then used to insert each of  the  arriving
  182.  
  183. fragments  into  the  buffer  area  where the complete datagram is being
  184.  
  185. built up.  The arriving fragment is  described  by  fragment.first,  the
  186.  
  187. first  octet  of  the fragment, and fragment.last, the last octet of the
  188.  
  189. fragment.
  190.  
  191.  
  192.    1. Select the next hole  descriptor  from  the  hole  descriptor
  193.       list.  If there are no more entries, go to step eight.
  194.  
  195.    2. If fragment.first is greater than hole.last, go to step one.
  196.  
  197.    3. If fragment.last is less than hole.first, go to step one.
  198.  
  199.  
  200.          - (If  either  step  two  or  step three is true, then the
  201.            newly arrived fragment does not overlap with the hole in
  202.            any way, so we need pay no  further  attention  to  this
  203.            hole.  We return to the beginning of the algorithm where
  204.            we select the next hole for examination.)
  205.  
  206.  
  207.    4. Delete the current entry from the hole descriptor list.
  208.  
  209.  
  210.          - (Since  neither  step  two  nor step three was true, the
  211.            newly arrived fragment does interact with this  hole  in
  212.            some  way.    Therefore,  the current descriptor will no
  213.            longer be valid.  We will destroy it, and  in  the  next
  214.            two  steps  we  will  determine  whether  or  not  it is
  215.            necessary to create any new hole descriptors.)
  216.  
  217.  
  218.    5. If fragment.first is greater than hole.first, then  create  a
  219.       new  hole  descriptor "new_hole" with new_hole.first equal to
  220.       hole.first, and new_hole.last equal to  fragment.first  minus
  221.       one.
  222.  
  223.                                    5
  224.  
  225.  
  226.          - (If  the  test in step five is true, then the first part
  227.            of the original hole is not filled by this fragment.  We
  228.            create a new descriptor for this smaller hole.)
  229.  
  230.  
  231.    6. If fragment.last is less  than  hole.last  and  fragment.more
  232.       fragments   is  true,  then  create  a  new  hole  descriptor
  233.       "new_hole", with new_hole.first equal to  fragment.last  plus
  234.       one and new_hole.last equal to hole.last.
  235.  
  236.  
  237.          - (This   test  is  the  mirror  of  step  five  with  one
  238.            additional feature.  Initially, we did not know how long
  239.            the reassembled datagram  would  be,  and  therefore  we
  240.            created   a   hole   reaching  from  zero  to  infinity.
  241.            Eventually, we will receive the  last  fragment  of  the
  242.            datagram.    At  this  point, that hole descriptor which
  243.            reaches from the last octet of the  buffer  to  infinity
  244.            can  be discarded.  The fragment which contains the last
  245.            fragment indicates this fact by a flag in  the  internet
  246.            header called "more fragments".  The test of this bit in
  247.            this  statement  prevents  us from creating a descriptor
  248.            for the unneeded hole which describes the space from the
  249.            end of the datagram to infinity.)
  250.  
  251.  
  252.    7. Go to step one.
  253.  
  254.    8. If the hole descriptor list is now empty, the datagram is now
  255.       complete.  Pass it on to the higher level protocol  processor
  256.       for further handling.  Otherwise, return.
  257.  
  258.  
  259.      4.  Part Two:  Managing the Hole Descriptor List
  260.  
  261.  
  262.      The  main  complexity  in  the  eight  step  algorithm above is not
  263.  
  264. performing the arithmetical tests, but in adding  and  deleting  entries
  265.  
  266. from  the  hole descriptor list.  One could imagine an implementation in
  267.  
  268. which the storage management package was  many  times  more  complicated
  269.  
  270. than  the rest of the algorithm, since there is no specified upper limit
  271.  
  272. on the number of hole descriptors which will exist for a datagram during
  273.  
  274. reassembly.   There  is  a  very  simple  way  to  deal  with  the  hole
  275.  
  276. descriptors, however.  Just put each hole descriptor in the first octets
  277.  
  278.                                    6
  279.  
  280.  
  281. of  the  hole  itself.    Note  that by the definition of the reassembly
  282.  
  283. algorithm, the minimum size of  a  hole  is  eight  octets.    To  store
  284.  
  285. hole.first  and  hole.last  will presumably require two octets each.  An
  286.  
  287. additional two octets will be required to thread together the entries on
  288.  
  289. the hole descriptor list.  This leaves at least two more octets to  deal
  290.  
  291. with implementation idiosyncrasies.
  292.  
  293.  
  294.      There  is  only  one obvious pitfall to this storage strategy.  One
  295.  
  296. must execute the eight step algorithm above before copying the data from
  297.  
  298. the fragment into the reassembly buffer.  If one were to copy  the  data
  299.  
  300. first,  it might smash one or more hole descriptors.  Once the algorithm
  301.  
  302. above has been run, any hole descriptors which are about to  be  smashed
  303.  
  304. have already been rendered obsolete.
  305.  
  306.  
  307.      5.  Loose Ends
  308.  
  309.  
  310.      Scattering  the  hole  descriptors throughout the reassembly buffer
  311.  
  312. itself requires that they be threaded onto some sort  of  list  so  that
  313.  
  314. they can be found.  This in turn implies that there must be a pointer to
  315.  
  316. the head of the list.  In many cases, this pointer can be stored in some
  317.  
  318. sort  of  descriptor block which the implementation associates with each
  319.  
  320. reassembly buffer.  If  no  such  storage  is  available,  a  dirty  but
  321.  
  322. effective  trick  is  to  store  the  head  of the list in a part of the
  323.  
  324. internet header in the reassembly buffer which is no longer needed.   An
  325.  
  326. obvious location is the checksum field.
  327.  
  328.  
  329.      When  the final fragment of the datagram arrives, the packet length
  330.  
  331. field in the internet header should be filled in.
  332.  
  333.                                    7
  334.  
  335.  
  336.      6.  Options
  337.  
  338.  
  339.      The preceding description made one unacceptable simplification.  It
  340.  
  341. assumed that there were no internet options associated with the datagram
  342.  
  343. being  reassembled.    The  difficulty  with  options  is that until one
  344.  
  345. receives the first fragment of the datagram, one cannot tell how big the
  346.  
  347. internet header will be.  This is because,  while  certain  options  are
  348.  
  349. copied  identically  into  every  fragment of a datagram, other options,
  350.  
  351. such as "record route", are put in the first fragment only.  (The "first
  352.  
  353. fragment"  is  the  fragment  containing  octet  zero  of  the  original
  354.  
  355. datagram.)
  356.  
  357.  
  358.      Until  one  knows how big the internet header is, one does not know
  359.  
  360. where to copy the data from each fragment into  the  reassembly  buffer.
  361.  
  362. If  the  earliest  fragment  to arrive happens to be the first fragment,
  363.  
  364. then this is no problem.  Otherwise, there are two  solutions.    First,
  365.  
  366. one  can  leave  space in the reassembly buffer for the maximum possible
  367.  
  368. internet header.  In fact, the  maximum  size  is  not  very  large,  64
  369.  
  370. octets.    Alternatively,  one can simply gamble that the first fragment
  371.  
  372. will contain no options.  If, when the first fragment  finally  arrives,
  373.  
  374. there  are  options,  one  can  then  shift  the  data  in  the buffer a
  375.  
  376. sufficient distance for allow for them.  The only peril in  copying  the
  377.  
  378. data  is  that  one  will  trash  the  pointers  that  thread  the  hole
  379.  
  380. descriptors together.  It is easy to see how to untrash the pointers.
  381.  
  382.  
  383.      The source and record route options have  the  interesting  feature
  384.  
  385. that,  since  different  fragments  can follow different paths, they may
  386.  
  387. arrive with different return routes  recorded  in  different  fragments.
  388.  
  389.                                    8
  390.  
  391.  
  392. Normally,  this  is  more information than the receiving Internet module
  393.  
  394. needs.  The specified procedure is to take the return route recorded  in
  395.  
  396. the first fragment and ignore the other versions.
  397.  
  398.  
  399.      7.  The Complete Algorithm
  400.  
  401.  
  402.      In addition to the algorithm described above there are two parts to
  403.  
  404. the reassembly process.  First, when a fragment arrives, it is necessary
  405.  
  406. to  find  the  reassembly  buffer  associated  with that fragment.  This
  407.  
  408. requires some  mechanism  for  searching  all  the  existing  reassembly
  409.  
  410. buffers.   The correct reassembly buffer is identified by an equality of
  411.  
  412. the following fields:  the  foreign  and  local  internet  address,  the
  413.  
  414. protocol ID, and the identification field.
  415.  
  416.  
  417.      The  final  part  of  the  algorithm  is  some  sort of timer based
  418.  
  419. mechanism which decrements the time to  live  field  of  each  partially
  420.  
  421. reassembled  datagram,  so that incomplete datagrams which have outlived
  422.  
  423. their usefulness can be detected and deleted.  One can either  create  a
  424.  
  425. demon  which  comes alive once a second and decrements the field in each
  426.  
  427. datagram by one, or one can read the  clock  when  each  first  fragment
  428.  
  429. arrives,  and  queue  some  sort  of  timer  call, using whatever system
  430.  
  431. mechanism is appropriate, to reap the datagram when its time has come.
  432.  
  433.  
  434.      An implementation of the complete algorithm  comprising  all  these
  435.  
  436. parts  was  constructed  in BCPL as a test.  The complete algorithm took
  437.  
  438. less than one and one-half pages of listing, and generated approximately
  439.  
  440. 400 nova machine instructions.  That portion of the  algorithm  actually
  441.  
  442. involved with management of hole descriptors is about 20 lines of code.
  443.  
  444.                                    9
  445.  
  446.  
  447.      The   version  of  the  algorithm  described  here  is  actually  a
  448.  
  449. simplification of the author's original version, thanks to an insightful
  450.  
  451. observation by Elizabeth Martin at MIT.
  452.  
  453.  
  454.